


#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    string minWindow1(string s, string t)
    {
        int ns = s.size(), nt = t.size();

        if (ns < nt)
            return "";

        int cnt_s[128] = { 0 };
        int cnt_t[128] = { 0 };
        int beg = 0, len = INT_MAX;

        for (auto e : t)
        {
            ++cnt_t[e];
        }
        for (int lf = 0, rg = 0; rg < ns; ++rg)
        {
            ++cnt_s[s[rg]];

            while (lf <= rg && check(cnt_s, cnt_t))
            {
                int cursz = rg - lf + 1;
                if (cursz < len)
                {
                    beg = lf;
                    len = cursz;
                }
                --cnt_s[s[lf++]];
            }
        }

        return s.substr(beg, len);
    }

    string minWindow2(string s, string t)
    {
        int ns = s.size(), nt = t.size();

        if (ns < nt)
            return "";

        int beg = 0, len = INT_MAX;
        unordered_map<char, int> cnt_s, cnt_t;

        for (auto e : t)
        {
            ++cnt_t[e];
        }

        for (int lf = 0, rg = 0, cnt = 0; rg < ns; ++rg)
        {
            char cur = s[rg];
            if (cnt_t.count(cur) && ++cnt_s[cur] == cnt_t[cur])
                ++cnt;

            while (cnt == cnt_t.size())
            {
                int cur_sz = rg - lf + 1;
                cur = s[lf];

                if (cur_sz < len)
                {
                    beg = lf;
                    len = cur_sz;
                }

                if (cnt_t.count(cur) && cnt_s[cur] >= cnt_t[cur] && --cnt_s[cur] < cnt_t[cur])
                {
                    --cnt;
                }
                ++lf;
            }
        }

        return s.substr(beg, len == INT_MAX ? 0 : len);
    }

    string minWindow3(string s, string t)
    {
        int ns = s.size(), nt = t.size();

        if (ns < nt)
            return "";

        int beg = 0, len = INT_MAX;
        int cnt_s[68] = { 0 }, cnt_t[68] = { 0 };
        int cnt = unordered_set<char>(t.begin(), t.end()).size();

        for (auto e : t)
        {
            ++cnt_t[e - 'A'];
        }

        for (int lf = 0, rg = 0, mycnt = 0, index = 0; rg < ns; ++rg)
        {
            index = s[rg] - 'A';
            if (cnt_t[index] && ++cnt_s[index] == cnt_t[index])
                ++mycnt;

            while (cnt == mycnt)
            {
                int cur_sz = rg - lf + 1;
                if (cur_sz < len)
                {
                    beg = lf;
                    len = cur_sz;
                }

                index = s[lf] - 'A';
                if (cnt_t[index] && cnt_s[index] >= cnt_t[index] && --cnt_s[index] < cnt_t[index])
                {
                    --mycnt;
                }
                ++lf;
            }
        }

        return s.substr(beg, len == INT_MAX ? 0 : len);
    }

    int findPoisonedDuration(vector<int>& timeSeries, int duration)
    {
        int n = timeSeries.size();
        if (1 == n)
            return duration;

        int res = 0;
        for (int i = 0; i < n - 1; ++i)
        {
            if (duration + timeSeries[i] - 1 < timeSeries[i + 1])
                res += duration;
            else
                res += timeSeries[i + 1] - timeSeries[i];
        }
        res += duration;

        return res;
    }

    string convert(string s, int numRows)
    {
        int n = s.size();
        if (1 == numRows || n < 3 || n <= numRows)
            return s;

        string res;
        vector<vector<char>> vv(numRows, vector<char>(n, '1'));

        for (int i = 0, j = 0, index = 0; index < n;)
        {
            if (0 == j%(numRows - 1))
            {
                while (i < numRows)
                {
                    vv[i++][j] = s[index++];
                    if (index >= n)
                        break;
                }
                ++j;
                --i, --i;
            }
            else
            {
                for (int k = 0; k < numRows - 2; ++k)
                {
                    vv[i--][j++] = s[index++];
                    if (index >= n)
                        break;
                }
            }
        }

        for (int i = 0; i < numRows; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (vv[i][j] != '1')
                    res += vv[i][j];
            }
        }

        return res;
    }

private:
    bool check(int* cnt_s, int* cnt_t)
    {
        for (int i = 0; i < 128; ++i)
        {
            if (cnt_t[i] && cnt_t[i] > cnt_s[i])
                return false;
        }

        return true;
    }
};

void Test1()
{
    string s = "aa", t = "aa";
    cout << Solution().minWindow3(s, t) << endl;
    cout << Solution().convert(string("PAYPALISHIRING"), 3) << endl;
}

int main()
{
    Test1();

	return 0;
}